package com.leetcode;

import java.util.*;
import java.util.stream.Collectors;

/**
 * 954. 二倍数对数组
 *
 * @author fy
 * @date 2022/4/1 15:36
 */
public class Solution954 {

    public boolean canReorderDoubled(int[] arr) {
        List<Integer> list = Arrays.stream(arr).boxed().sorted(Comparator.comparingInt(Math::abs)).collect(Collectors.toList());
        Map<Integer, Integer> map = new HashMap<>(arr.length / 2);
        for (int i = 0; i < list.size(); i++) {
            if (map.containsKey(list.get(i))) {
                map.put(list.get(i), map.get(list.get(i)) + 1);
            } else {
                map.put(list.get(i), 1);
            }
        }
        for (int i = 0; i < list.size(); i++) {
            if (map.get(list.get(i)) == 0) {
                continue;
            }
            if (!map.containsKey(list.get(i) * 2)) {
                return false;
            }
            if (map.get(list.get(i) * 2) <= 0) {
                return false;
            }
            map.put(list.get(i), map.get(list.get(i)) - 1);
            map.put(list.get(i) * 2, map.get(list.get(i) * 2) - 1);
        }
        return true;
    }

    public static void main(String[] args) {
        int[] arr = new int[] {2,4,0,0,8,1};
        new Solution954().canReorderDoubled(arr);
    }

}
